package exams.search;

public class ArraySolution {

    /**
     * 二分查找-I
     *
     * 请实现无重复数字的升序数组的二分查找
     * 给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
     * */
    public int search (int[] nums, int target) {
        // write code here
        int l = 0;
        int r = nums.length - 1;
        while(l <= r) {
            int m = (l + r) / 2;
            if(nums[m] == target) {
                return m;
            } else if(target < nums[m]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return -1;
    }

    /**
     * 二维数组中的查找
     *
     * 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     * [
     * [1,2,8,9],
     * [2,4,9,12],
     * [4,7,10,13],
     * [6,8,11,15]
     * ]
     * 给定 target= 7，返回true。
     * 给定target=3，返回false。
     * */
    public boolean Find (int target, int[][] array) {
        // write code here
        int xl = array.length;
        int yl = array[0].length;
        int x = 0;
        int y = yl - 1;

        while(x < xl && y >= 0) {
            if(array[x][y] > target) {
                y --;
            } else if(array[x][y] < target) {
                x ++ ;
            } else {
                return true;
            }
        }

        return false;
    }

    /**
     * 寻找峰值
     *
     * 给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
     * 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
     * 2.假设nums[-1] = nums[n] =−∞−∞
     * 3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
     * 4.你可以使用O(logN)的时间复杂度实现此问题吗？
     * 如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰
     *
     * 输入：
     * [2,4,1,2,7,8,4]
     * 返回值：
     * 1
     * 说明：
     * 4和8都是峰值元素，返回4的索引1或者8的索引5都可以
     * */
    public int findPeakElement (int[] nums) {
        // write code here
        int r = nums.length - 1;
        int l = 0;

        while(l < r) {
            int m = (r + l) / 2;
            if(nums[m] > nums[m + 1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        return r;
    }


    /**
     * 数组中的逆序对
     *
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
     * 数据范围： 对于50%的数据,size≤104
     * 对于100%的数据,size≤105
     * 数组中所有数字的值满足0≤val≤109
     * 要求：空间复杂度O(n)，时间复杂度O(nlogn)
     * 题目保证输入的数组中没有的相同的数字
     *
     * 输入：
     * [1,2,3,4,5,6,7,0]
     * 返回值：
     * 7
     * */
    public int InversePairs (int[] nums) {
        // write code here
        int res = mergeSort(0, nums.length - 1, nums, new int[nums.length]);
        return res%Z;
    }
    private final static int Z = 1000000007;
    private static int count = 0;
    public int mergeSort(int l, int r, int[] nums, int[] temp) {
        if(l >= r) {
            return 0;
        }
        int m = (l + r) / 2;

        int res = (mergeSort(l, m, nums, temp) + mergeSort(m + 1, r, nums, temp)) % Z;

        for(int k=l; k<=r; k++) {
            temp[k] = nums[k];
        }
        int p1 = l, p2 = m + 1;
        int k;
        for(k = l; k <= r; k++) {
            if(p1 > m || p2 > r) {
                break;
            }
            if(temp[p1] <= temp[p2]) {
                nums[k] = temp[p1++];
            } else {
                nums[k] = temp[p2++];
                res = res + m - p1 + 1;
            }
        }

        while(p1 <= m) {
            nums[k++] = temp[p1++];
        }
        while(p2 <= r) {
            nums[k++] = temp[p2++];
        }

        return res;
    }

    /**
     * 旋转数组的最小数字
     *
     * 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
     *
     *
     * */
    public int minNumberInRotateArray (int[] nums) {
        // write code here
        int p1 = 0;
        int p2 = nums.length - 1;

        while(p1 < p2) {
            int m = (p1 + p2) / 2;
            if(nums[m] > nums[p2]) {
                p1 = m + 1;
            } else if(nums[m] < nums[p2]) {
                p2 = m;
            } else {
                p2 --;
            }
        }
        return nums[p1];
    }

    /**
     * 比较版本号
     *
     * 每个版本号至少包含1个修订号。
     * 修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。
     * 比较规则：
     * 一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"0.1"和"0.01"的版本号是相等的
     * 二. 如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，"1.1"的版本号小于"1.1.1"。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1
     * 三. version1>version2返回1，如果version1<version2返回-1，不然返回0.
     *
     * 数据范围：
     * 1<=version1.length,version2.length<=1000
     * version1和version2的修订号不会超过int的表达范围，即不超过32 位整数的范围
     *
     * 进阶： 空间复杂度O(1)， 时间复杂度O(n)
     * */
    public int compare (String version1, String version2) {
        // write code here
        String[] vArr1 = version1.split("\\.");
        String[] vArr2 = version2.split("\\.");

        int p = 0;
        while(p < vArr1.length && p < vArr2.length) {
            if(Integer.valueOf(vArr1[p]) > Integer.valueOf(vArr2[p])) {
                return 1;
            } else if (Integer.valueOf(vArr1[p]) < Integer.valueOf(vArr2[p])){
                return -1;
            } else {
                p++;
            }
        }
        while(vArr1.length > p) {
            if(Integer.valueOf(vArr1[p]) != 0) {
                return 1;
            } else {
                p ++;
            }
        }
        while(vArr2.length > p) {
            if(Integer.valueOf(vArr2[p]) != 0) {
                return 1;
            } else {
                p ++;
            }
        }

        return 0;
    }
}
